home *** CD-ROM | disk | FTP | other *** search
/ IRIX Base Documentation 2002 November / SGI IRIX Base Documentation 2002 November.iso / usr / share / catman / p_man / cat3c / lsearch.z / lsearch
Encoding:
Text File  |  2002-10-03  |  5.5 KB  |  133 lines
  1.  
  2.  
  3.  
  4. LLLLSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))                                                        LLLLSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))
  5.  
  6.  
  7.  
  8. NNNNAAAAMMMMEEEE
  9.      lsearch, lfind - linear search and update
  10.  
  11. SSSSYYYYNNNNOOOOPPPPSSSSIIIISSSS
  12.      ####iiiinnnncccclllluuuuddddeeee <<<<ssssttttddddiiiioooo....hhhh>>>>
  13.      ####iiiinnnncccclllluuuuddddeeee <<<<sssseeeeaaaarrrrcccchhhh....hhhh>>>>
  14.  
  15.      vvvvooooiiiidddd ****llllsssseeeeaaaarrrrcccchhhh ((((((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****))))kkkkeeeeyyyy,,,, ((((vvvvooooiiiidddd ****))))bbbbaaaasssseeee,,,,
  16.                     ssssiiiizzzzeeee____tttt ****nnnnmmmmeeeemmmmbbbb,,,, ssssiiiizzzzeeee____tttt ssssiiiizzzzeeee,,,,
  17.                     iiiinnnntttt ((((****ccccoooommmmppppaaaarrrr))))((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****,,,, ccccoooonnnnsssstttt vvvvooooiiiidddd ****))))))));;;;
  18.  
  19.      vvvvooooiiiidddd ****llllffffiiiinnnndddd ((((((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****))))kkkkeeeeyyyy,,,, ((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****))))bbbbaaaasssseeee,,,,
  20.                   ssssiiiizzzzeeee____tttt ****nnnnmmmmeeeemmmmbbbb,,,, ssssiiiizzzzeeee____tttt ssssiiiizzzzeeee,,,,
  21.                   iiiinnnntttt ((((****ccccoooommmmppppaaaarrrr))))((((ccccoooonnnnsssstttt vvvvooooiiiidddd ****,,,, ccccoooonnnnsssstttt vvvvooooiiiidddd ****))))))));;;;
  22.  
  23. DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
  24.      _l_s_e_a_r_c_h is a linear search routine generalized from Knuth (6.1) Algorithm
  25.      S.  It returns a pointer into a table indicating where a datum may be
  26.      found.  If the datum does not occur, it is added at the end of the table.
  27.      KKKKeeeeyyyy points to the datum to be sought in the table.  BBBBaaaasssseeee points to the
  28.      first element in the table.  NNNNmmmmeeeemmmmbbbb points to an integer containing the
  29.      current number of elements in the table.  The integer is incremented if
  30.      the datum is added to the table.  _S_i_z_e is the size of the key in bytes
  31.      (_s_i_z_e_o_f (*_k_e_y)).  CCCCoooommmmppppaaaarrrr is the name of the comparison function which the
  32.      user must supply (_s_t_r_c_m_p, for example).  It is called with two arguments
  33.      that point to the elements being compared.  The function must return zero
  34.      if the elements are equal and non-zero otherwise.
  35.  
  36.      _L_f_i_n_d is the same as _l_s_e_a_r_c_h except that if the datum is not found, it is
  37.      not added to the table. Instead, a NULL pointer is returned.
  38.  
  39. NNNNOOOOTTTTEEEESSSS
  40.      The pointers to the key and the element at the base of the table should
  41.      be of type pointer-to-element, and cast to type pointer-to-character.
  42.      The comparison function need not compare every byte, so arbitrary data
  43.      may be contained in the elements in addition to the values being
  44.      compared.
  45.      Although declared as type pointer-to-character, the value returned should
  46.      be cast into type pointer-to-element.
  47.  
  48. EEEEXXXXAAAAMMMMPPPPLLLLEEEE
  49.      This fragment will read in less than TABSIZE strings of length less than
  50.      ELSIZE and store them in a table, eliminating duplicates.
  51.  
  52.           #include <stdio.h>
  53.           #include <search.h>
  54.  
  55.           #define TABSIZE 50
  56.           #define ELSIZE 120
  57.  
  58.                char line[ELSIZE], tab[TABSIZE][ELSIZE], *lsearch( );
  59.                unsigned nel = 0;
  60.  
  61.  
  62.  
  63.                                                                         PPPPaaaaggggeeee 1111
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70. LLLLSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))                                                        LLLLSSSSEEEEAAAARRRRCCCCHHHH((((3333CCCC))))
  71.  
  72.  
  73.  
  74.               int strcmp( );
  75.                . . .
  76.                while (fgets(line, ELSIZE, stdin) != NULL &&
  77.                   nel < TABSIZE)
  78.                     (void) lsearch(line, (char *)tab, &nel,
  79.                            ELSIZE, strcmp);
  80.                . . .
  81.  
  82. SSSSEEEEEEEE AAAALLLLSSSSOOOO
  83.      bsearch(3C), hsearch(3C), string(3C), tsearch(3C).
  84.  
  85. DDDDIIIIAAAAGGGGNNNNOOOOSSSSTTTTIIIICCCCSSSS
  86.      If the searched for datum is found, both _l_s_e_a_r_c_h and _l_f_i_n_d return a
  87.      pointer to it.  Otherwise, _l_f_i_n_d returns NULL and _l_s_e_a_r_c_h returns a
  88.      pointer to the newly added element.
  89.  
  90. BBBBUUUUGGGGSSSS
  91.      Undefined results can occur if there is not enough room in the table to
  92.      add a new item.
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.                                                                         PPPPaaaaggggeeee 2222
  130.  
  131.  
  132.  
  133.